package com.kavinz.algo.stack;

/**
 * 
 * <Cracking the coding interview><br>
 * Exercise 3.4:in the classic problem of the Towers of Hanoi, you have 3 rods
 * and N disks of different sizes which can slide on to any tower The puzzle
 * starts with disks sorted in ascending order of size from top to bottom (e g ,
 * each disk sits on top of an even larger one)<br>
 * You have the following constraints: <li>(A) Only one disk can be moved at a
 * time</li><li>(B) A disk is slid off the top of one rod onto the next rod</li>
 * <li>(C) A disk can only be placed on top of a larger disk <br>
 * Write a program to move the disks from the first rod to the last using Stacks
 * </li>
 * 
 * @author Kevin Zhao
 * 
 */
public class HanoiTower {
	LinkedListStack[] rods = new LinkedListStack[3];
	private int DISK_AMOUNT = 5;
	private int ROD_AMOUNT = 3;

	public HanoiTower() {

		for (int i = 0; i < ROD_AMOUNT; i++) {
			LinkedListStack rod = new LinkedListStack();
			rods[i] = rod;
		}
		for (int i = DISK_AMOUNT; i > 0; i--) {
			rods[0].push(i);
		}

	}

	public HanoiTower(int diskAmount, int rodAmount) {
		this();
		this.DISK_AMOUNT = diskAmount;
		this.ROD_AMOUNT = rodAmount;
	}

	public void play()
	{
		move(0,rods.length-1,1,DISK_AMOUNT);
	}
	private void move(int sourceIndex,int destinationIndex,int tmpIndex,int n)
	{
		LinkedListStack source = rods[sourceIndex];
		LinkedListStack destination = rods[destinationIndex];
		LinkedListStack tmp = rods[tmpIndex];
		//recursion termination condition
		if(n==1)
		{
			destination.push(source.pop());
			System.out.println("==============>");
			System.out.println("A:"+rods[0].toString());
			System.out.println("B:"+rods[1].toString());
			System.out.println("C:"+rods[2].toString());
			return;
		}
		
		//move n-1 disks from sourceRod to tmpRod via destinationRod
		move(sourceIndex,tmpIndex,destinationIndex,n-1);
		//move the nth disk from sourceRod to destinationRod directly
		move(sourceIndex,destinationIndex,tmpIndex,1);
		//move n-1 disks from tmpRod to destinationRod via sourceRod
		move(tmpIndex,destinationIndex,sourceIndex,n-1);
	}
	public static void main(String[] args) {
		HanoiTower game = new HanoiTower();
		game.play();
	}
}
